package array.leetcode.easy;

/**
 * @author bruin_du
 * @description 山峰数组的顶部
 * @date 2022/8/22 22:08
 **/
public class OfferII069_PeakIndexInMountainArray {
    public int peakIndexInMountainArray(int[] arr) {
        // 二分法，采用一边逼近的方法
        method1(arr);

        // 三分法，每次抛弃三分之一
        return method2(arr);
    }

    private int method1(int[] arr) {
        int n = arr.length;
        int l = 1, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid - 1] > arr[mid]) r = mid - 1;
            else l = mid;
        }
        return l;

//        int n = arr.length;
//        int l = 0, r = n - 2;
//        while (l < r) {
//            int mid = l + r - 1 >> 1;
//            if (arr[mid] < arr[mid + 1]) l = mid + 1;
//            else r = mid;
//        }
//        return l;
    }

    private int method2(int[] arr) {
        int n = arr.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int m1 = l + (r - l) / 3;
            int m2 = r - (r - l) / 3;
            if (arr[m1] > arr[m2]) r = m2 - 1;
            else l = m1 + 1;
        }
        return l;
    }
}
